Stockholm 1994:

    IOI. 15 (Ceasuri). Noua ceasuri cu cte o singura limba sunt asezate ntr-un tablou 3x3.
Se definesc 9 modalitati diferite de a nvrti cadranele acestor ceasuri, modalitati date de figura
urmatoare:






Fiecare astfel de modalitate (codificata cu numere ntre 0 si 9) este
numita miscare. Efectuarea unei miscari semnifica rotirea
cadranelor situate n zona hasurata cu 90o.
Intrare: Se citesc 9 numere care vor reprezenta pozitiile de start ale
cadranelor ceasurilor din tablou. Marcarea va fi: 0 pentru limba
ceasului asezata la ora 12, 1 pentru ora 3, 2 pentru ora 6 si 3
pentru ora 9.
Iesirea: va fi cea mai scurta secventa de miscari necesare pentru a
aduce limbile tuturor ceasurilor la ora 12.
Exemplu: pentru intrarea
3 3 0
2 2 2
2 1 2
iesirea este secventa
5849
=========================================
Solutie 1 (Vlad Atanasiu):

uses crt;
const transformare:array [1..9,1..3,1..3] of byte=
      (((1,1,0),(1,1,0),(0,0,0)),((1,1,1),(0,0,0),(0,0,0)),((0,1,1),(0,1,1),(0,0,0)),
       ((1,0,0),(1,0,0),(1,0,0)),((0,1,0),(1,1,1),(0,1,0)),((0,0,1),(0,0,1),(0,0,1)),
       ((0,0,0),(1,1,0),(1,1,0)),((0,0,0),(0,0,0),(1,1,1)),((0,0,0),(0,1,1),(0,1,1)));
      valoare:array [1..9] of byte=(4,3,4,3,5,3,4,3,4);
type matrice=array [1..3,1..3] of byte;
     vector=array [1..9] of byte;
var x:matrice;
    lista,solutie:vector;
    i,j,sc,nminim,kk:byte;

procedure transforma(var ce:matrice;cum:byte);
{ transforma matricea ce cu transformarea nr. cum }
var i,j:integer;
begin
for i:=1 to 3 do for j:=1 to 3 do
    ce[i,j]:=(ce[i,j]+transformare[cum,i,j]) mod 4;
end;

function zero(g:matrice):boolean;
{ intoarce TRUE daca toate elementele matricii sunt 0 }
var i,j:byte;
    r:boolean;
begin
zero:=false;
for i:=1 to 3 do for j:=1 to 3 do
    begin
    r:=(g[i,j]<>0);
    if r then exit;
    end;
zero:=not r;
end;

procedure verifica(n:byte);
var i,j:byte;
    g:matrice;
begin
if n<nminim then
   begin
   for i:=1 to 3 do for j:=1 to 3 do g[i,j]:=x[i,j];
   for i:=1 to n do
       { aplica matricii de proba toate transformarile din lista }
       transforma(g,lista[i]);
   if zero(g) then
      begin
      nminim:=n;
      for i:=1 to n do solutie[i]:=lista[i];
      end;
   end;
end;

procedure complementar(g:matrice);
var s,i,j:byte;
begin
sc:=0;
for i:=1 to 3 do for j:=1 to 3 do sc:=sc+(4-g[i,j]) mod 4;
end;

procedure calc(suma:integer;index:byte);
var i:integer;
begin
if suma<>sc+kk*4 then
   begin
   for i:=1 to 9 do
       begin
       lista[index]:=i;
       if valoare[i]+suma<=sc+kk*4 then
          calc(suma+valoare[i],index+1);
       end;
   end
else verifica(index-1);
end;

begin
clrscr;
assign(input,'input.i15');
reset(input);
for i:=1 to 3 do
    begin
    for j:=1 to 3 do read(input,x[i,j]);
    readln(input);
    end;
close(input);
for i:=1 to 9 do solutie[i]:=0;
complementar(x); { calculeaza suma complementara }
nminim:=9;
kk:=0;
repeat
      calc(0,1);
      inc(kk);
      writeln(kk);
until (nminim<>9) or (kk>9);
if solutie[1]<>0 then for i:=1 to nminim do write(solutie[i])
else writeln('Nu exista solutie.');
end.
=====================================
Solutia 2: (Petric Vlad, Lic.Informatica Brasov)

Algoritm euristic care da o solutie in timp constant.

	Se observa ca daca aplicam o serie de transformari unei configuratii
        initiale, ordinea in care acestea sunt realizate nu are nici o
        importanta (orice permutare a sabloanelor intr-o serie conduce la
        acelasi rezultat, de exemplu: 4-5-8-9 si 5-4-8-9).  Deci, pentru
        simplitate si claritate, putem considera doar seriile crescatoare de
        transformari (vom prefera seria 1-1-2-4 in loc de 1-4-2-1). De
        asemenea, o serie se va pastra intr-un vector A cu 9 elemente, unde
        A[i] ne arata cate transformari sunt efectuate cu sablonul "i"; de
        exemplu, seriei 1-1-1-3-3-5-7-8-9-9 ii va corespunde vectorul
        (3,0,2,0,1,0,1,1,2).  O alta observatie importanta este aceea ca 4
        transformari de acelasi tip se anuleaza (ceasurile care sunt
        afectate sunt rotite cu 360 de grade, deci revin in pozitia
        initiala).  Vom numi "serie elementara de transformari" o serie in
        care orice transformare apare de cel mult 3 ori.  Orice serie se
        poate reduce la una elementara, aplicand fiecarui element din
        vectorul ce o caracterizeaza operatia modulo 4. Deci nu va mai
        trebui sa lucram decat cu serii elementare.  In continuare se vor
        prezenta si demonstra doua afirmatii importante, care conduc la un
        algoritm foarte simplu.

	1: Din orice configuratie putem ajunge in orice alta configuratie
        printr-o serie elementara de transformari.  Pentru a demonstra
        aceasta afirmatie, vom arata ca exista pentru fiecare dintre
        ceasurile unei configuratii o serie elementara, care dupa ce a fost
        aplicata in intregime, a modificat doar ceasul respectiv cu o
        singura pozitie (o rotatie de 90 de grade). De exemplu, seria ce
        modifica doar primul ceas este (3,3,3,3,3,2,3,2,0), pe al doilea
        (2,3,2,3,2,3,1,0,1), pe cel din mijloc (2,3,2,3,1,3,2,3,2). Pentru
        celelalte elemente, seriile se determina prin simetrie. Toate aceste
        serii au fost deduse din sisteme de ecuatii ce contin operatia
        modulo. Pentru a nu ne pierde in detalii, se va prezenta in final
        modul in care s-au dedus rezultatele (foarte importante) de mai sus. 
        Astfel, pentru a trece dintr-o configuratie in alta, vom aplica
        fiecarui ceas seria ce il afecteaza doar pe acesta de cate ori este
        nevoie. Seria de transformari ce rezulta o vom reduce la una
        elementara (prin procedeul descris anterior). Deci afirmatia este
        demonstrata.

	2: Fie c1 si c2 doua configuratii oarecare distincte. Exista o serie
        elementara si numai una care transforma pe c1 in c2.  Afirmatia 1 ne
        asigura ca exista o astfel de serie; ramane de aratat ca ea este
        unica. In total sunt 4 la 9 = 2 la 18 configuratii posibile ( avand
        9 ceasuri si 4 pozitii pentru fiecare ceas ) si (4 la 9)-1=(2 la
        18)-1 serii elementare distincte (vectorul (0,0,0,0,0,0,0,0,0) nu se
        ia in considerare intrucat nu reprezinta nici o transformare).
        Astfel, daca scoatem c1 din multimea tuturor configuratiilor
        posibile raman (2 la 18)-1 configuratii, numar ce coincide cu numarul
        tuturor seriilor elementare, deci nu se poate ajunge din c1 in c2
        prin 2 serii distincte ( pentru ca stim din afirmatia 1 ca trebuie
        sa se poata ajunge in orice configuratie ).

	In consecinta, putem formula urmatorul algoritm: Este suficient sa
        gasim o serie oarecare care sa rezolve problema.  Cum gasim insa o
        astfel de serie ? Vom aduce pe rand fiecare ceas pe pozitia 0
        utilizand seriile care modifica un singur ceas (prezentate
        anterior); vom reuni toate transformarile (aduna vectorii
        corespunzatori) intr-o singura serie.  Transformam seria gasita
        intr-una elementara (ce va fi sigur o solutie problemei; restul
        solutiilor se pot obtine generand toate permutarile solutiei).
 
	Programul

const a:array[1..9,1..9] of byte=((3,3,3,3,3,2,3,2,0),(2,3,2,3,2,3,1,0,1),
                                  (3,3,3,2,3,3,0,2,3),(2,3,1,3,2,0,2,3,1),
                                  (2,3,2,3,1,3,2,3,2),(1,3,2,0,2,3,1,3,2),
                                  (3,2,0,3,3,2,3,3,3),(1,0,1,3,2,3,2,3,2),
                                  (0,2,3,2,3,3,3,3,3));

var y:array[1..9] of byte;
    aux,i,j:byte;
    f:text;

begin
  writeln;
  assign(f,'INPUT.TXT');
  reset(f);
  for i:=1 to 9 do
    y[i]:=0;
  for i:=1 to 9 do begin
    read(f,aux);
    for j:=1 to 9 do
      inc(y[j],(4-aux)*a[i,j]);
  end;
  for i:=1 to 9 do
    for j:=1 to y[i] mod 4 do
      write(i);
end.

	Prezentam modul in care se face deducerea seriilor corespunzatoare
        unui ceas.

	De exemplu, dorim sa modificam doar primul ceas. Se observa ca
        fiecare din ceasuri este afectat de mai multe transformari. Ceasul 1
        este modificat de sabloanele 1, 2 si 4. Avand vectorul a ce
        caracterizeaza o serie elementara, putem scrie urmatorul sistem de
        ecuatii, fiecare din acestea reprezentand transformarea pe care o
        sufera un ceas (pentru un alt ceas, putem modifica partea dreapta
        ecuatiei corespunzatoare, de exemplu, pentru a modifica ceasul 2 vom
        pune " = 1" in ecuatia 2. si 0 in rest):



1).	(a[1]+a[2]+a[4]) mod 4 = 1
2).	(a[1]+a[2]+a[3]+a[5]) mod 4 = 0
3).	(a[2]+a[3]+a[6]) mod 4 = 0
4).	(a[1]+a[4]+a[7]+a[5]) mod 4 = 0
5).	(a[1]+a[3]+a[5]+a[7]+a[9]) mod 4 = 0
6).	(a[3]+a[5]+a[6]+a[9]) mod 4 = 0
7).	(a[4]+a[7]+a[8]) mod 4  = 0
8).	(a[5]+a[7]+a[8]+a[9]) mod 4 = 0
9).	(a[6]+a[8]+a[9]) mod 4 = 0

unde, desigur, a[i] din {0,1,2,3}

Din aritmetica operatiei modulo avem urmatoarea formula:
	(a + b) mod k = (a mod k + b mod k) mod k
De aici rezulta ca daca     (a+b) mod k = (a + b') mod k, 
		    atunci    b mod k = b' mod k.
Etape:	
	a). Luam ecuatiile 2. si 3. :
		(a[2]+a[3]+a[5]+a[1]) mod 4 = 0
		(a[2]+a[3]+a[6]) mod 4 = 0
	b). Din acestea rezulta ca a[6] = (a[5]+a[1]) mod 4
	c). Avem ecuatia 9: (a[6]+a[8]+a[9]) mod 4 = 0
	d). Din b. si c. rezulta ca:(a[1]+a[5]+a[8]+a[9]) mod 4 = 0
	e). Avem ecuatia 8: (a[7]+a[5]+a[8]+a[9]) mod 4 = 0
	f). Din d. si e. rezulta ca a[1] = a[7]
	g). In mod analog rezulta ca a[1] = a[3] = a[7];
					a[2] = a[4] si 
					a[6] = a[8]
	h). Sistemul l-am rezolvat prin incercari.
==========================================================
Solutia 3 (Vasile Butnaru, Timisoara)
  Solutia este Branch&Bound.
  Se construiesc doua liste, un element al unei liste reprezinta
o configuratie de ceasuri la un moment, avand legaturi catre nodul
din care provine prin constructia permisa, si legaturi catre urmat.
noduri din lista. Lista open=lista nodurilor active, neexpandate
prin operatia permisa de sabloane. Lista clos=lista nodurilor
expandate deja.
  Initial lista open=nodul initial. Cat timp nu s-a ales nodul
configuratiei finale sau lista open este nevida se executa:
 se alege din open nodul cu functia f minima (functia f "arata"
cat de optim este nodul dat, e o functie optimista), se expandeaza
acest nod (se obtin nodurile prin folosirea sabloanelor), iar pt.
fiecare din noduri se verifica daca se afla in open (daca da, daca
acum e mai optim se inlocuieste cu actuala situatie), daca e in clos
atunci daca acum e mai optim il bagam in open altfel il lasam acolo.
Daca open=nil atunci nu exista solutie.
*)

{$G+,X+,F+} uses crt;
type
	atom		=	integer;
	patrat		=	array [1..3,1..3] of atom;
	plista		=	^lista;
	lista		=	record
		prev,tata,next	:plista;
                 {prev=anterior, liste dublu inlantuite}
		g,h		:atom;
                 {g=drumul pana aici de la nodul initial,
                 h=estimarea}
		a		:patrat;
                 {a=conf. de ceasuri}
		mut		:atom;
                 {mut=tipul sablonului care a fost folosit pt.
                  a ajunge aici}
	end;
const
	      nv:array [1..9] of atom=(4,3,4,3,5,3,4,3,4);
		py:array [1..9,1..5] of atom=(
			(1,2,1,2,0),
			(1,2,3,0,0),
			(2,3,2,3,0),
			(1,1,1,0,0),
			(2,1,2,3,2),
			(3,3,3,0,0),
			(1,2,1,2,0),
			(1,2,3,0,0),
			(2,3,2,3,0)
		);
		px:array [1..9,1..5] of atom=(
			(1,1,2,2,0),
			(1,1,1,0,0),
			(1,1,2,2,0),
			(1,2,3,0,0),
			(1,2,2,2,3),
			(1,2,3,0,0),
			(2,2,3,3,0),
			(3,3,3,0,0),
			(2,2,3,3,0)
		);
{
    matricele px si py contin sabloanele codificate.
}

var
		time1,time2	:longint;
		time		:longint absolute $0:$46c;
		a		:patrat;
		i,j,k,l,m,n	:atom;
		open,clos	:plista;
		p,p1,p2,p3,p4,p5:plista;
		fo		:text;
                salt            :atom;

procedure timp;
 begin {arata cat timp s-a rulat}
	time2:=time;
	assign(output,'con'); rewrite(output);
	writeln((time2-time1)/18.2:7:3,' secunde.');
	close(output);
 end;

function h(var a:patrat):atom;
  var s,i,j:atom;
 begin {aproximeaza efortul pana la sfarsit}
	s:=0;
	for i:=1 to 3 do
	  for j:=1 to 3 do
		if a[i,j]<>0 then s:=s+4-a[i,j];
	h:=s;
 end;

procedure muta(var d,s:patrat);
  var i,j:atom;
 begin {copiaza o configurate in alta}
	for i:=1 to 3 do
         for j:=1 to 3 do d[i,j]:=s[i,j];
 end;

procedure afis(p:plista);
 begin {afiseaza solutia pe baza legaturi tip tata}
	if p^.mut=0 then exit;
	afis(p^.tata);
	write(p^.mut);
 end;

procedure expand(var s,d:patrat;mut:atom);
  var i,k,l:atom;
 begin {expandeaza o configuratie cu sablonul}
	muta(d,s);
	for i:=1 to nv[mut] do
	begin
		k:=px[mut,i]; l:=py[mut,i];
		d[k,l]:=(d[k,l]+1) mod 4;
	end;
 end;

function egal(var s,d:patrat):boolean;
  var i,j:atom;
 begin {daca doua config. sunt identice}
	for i:=1 to 3 do
         for j:=1 to 3 do
          if s[i,j]<>d[i,j] then
	   begin egal:=false; exit; end;
	egal:=true;
 end;

  label baga_open;
begin {main}
	time1:=time;
	{$I-}
	assign(input,'input.txt'); reset(input);
	assign(output,'output.txt'); rewrite(output);
	if ioresult<>0 then
	begin
		writeln('Eroare la fisiere.'); halt;
	end;
	{$I+}
	for i:=1 to 3 do
	begin
		readln(a[i,1],a[i,2],a[i,3]);
	end;
	close(input);
	assign(fo,'con'); rewrite(fo);
	clos:=nil;
	new(open); open^.tata:=nil; open^.next:=nil;
        open^.prev:=nil; muta(open^.a,a); open^.g:=0;
        open^.h:=h(a); open^.mut:=0;
        {open=nodul initial}
while open<>nil do
begin
	asm 
		mov	ah,0fh
		int	10h
		mov	ax,0e2ah
		mov	bh,0
		int	10h
	end;
        {afiseaza o steluta pe ecran pt. ca iesirea standard
         e redirectata catre INPUT.TXT}
	p:=open^.next; p1:=open; with p1^ do i:=g+h;
	while p<>nil do
	begin {cautam din open cel mai bun nod}
		if p^.g+p^.h<i then
		begin
			p1:=p; with p^ do i:=g+h;
		end;
		p:=p^.next;
	end;
	p:=p1; {daca cel final afis. sol.}
	if p^.h=0 then begin
		afis(p); writeln; close(output);
                writeln(fo);close(fo); timp; halt;
	end;
	for i:=1 to 9 do
	begin {expandam cu cele 9 sabloane}
		expand(p^.a,a,i);
		p1:=open;
		while (p1<>nil) and (not egal(a,p1^.a))
                  do p1:=p1^.next;
		if p1<>nil then
		if p^.g+1<p1^.g then
		begin
			p1^.mut:=i; p1^.tata:=p;
                        p1^.g:=p^.g+1; continue;
		end else continue;
		p1:=clos;
		while (p1<>nil) and (not egal(p1^.a,a))
                     do p1:=p1^.next;
		if p1<>nil then begin
		if p1^.g<=p^.g+1 then continue;
		p3:=p1^.prev;
		if p3<>nil then
		begin
		  p3^.next:=p1^.next; p1^.next^.prev:=p3;
		end else
		begin
			clos:=p1^.next; clos^.prev:=nil;
		end;
		p1^.next:=open; open^.prev:=p1; open:=p1;
		p1^.g:=p^.g+1; p1^.tata:=p; p1^.mut:=i;
                continue; end;
		new(p3); muta(p3^.a,a); p3^.tata:=p;
                p3^.next:=open; open^.prev:=p3; open:=p3;
		p3^.g:=p^.g+1; p3^.h:=h(a); p3^.mut:=i;
	end;
	p2:=p^.prev;
	if p2=nil then
	begin {nodul din open e trecut in clos}
		open:=open^.next; open^.prev:=nil;
		p^.next:=clos; clos^.prev:=p; clos:=p;
	end else
	begin
		p2^.next:=p^.next; p^.next^.prev:=p2;
		p^.next:=clos; clos^.prev:=p; clos:=p;
	end;
end;
	close(output);
	timp;
end.
========================================
Solutia 4 (Mihai Stroe)

    Ordinea mutarilor nu conteaza. O mutare poate fi efectuata de 0,1,2,3 ori.
    Generam toate posibilitatile de efectuare de x(i) ori a fiecarei mutari
    (0<=x<=3); sunt 4^9=2^18 variante distincte, deci pentru a optimiza
    vom alege variante cu numar de mutari mai mic decit optimul partial.
    Nu este nevoie de o strategie mai performanta, programul fiind foarte
    rapid.

uses crt;
const mut:array[1..9,1..3,1..3]of byte=
      ( ( (1,1,0),
          (1,1,0),
          (0,0,0)  ),
        ( (1,1,1),
          (0,0,0),
          (0,0,0)  ),
        ( (0,1,1),
          (0,1,1),
          (0,0,0)  ),
        ( (1,0,0),
          (1,0,0),
          (1,0,0)  ),
        ( (0,1,0),
          (1,1,1),
          (0,1,0)  ),
        ( (0,0,1),
          (0,0,1),
          (0,0,1)  ),
        ( (0,0,0),
          (1,1,0),
          (1,1,0)  ),
        ( (0,0,0),
          (0,0,0),
          (1,1,1)  ),
        ( (0,0,0),
          (0,1,1),
          (0,1,1)  ));

type ar=array[1..3,1..3]of byte;
var init:ar;
    a:array[0..9]of ar;
    mm,st,sol:array[1..9]of integer;
    i,j,k,l,kk,m,mo,n:byte;
    s:string;
    f:text;

procedure react;
begin
  if m<mo then
     begin
       mo:=m;
       sol:=st;
     end;
end;

procedure calcul;
begin
      for i:=1 to 3 do
          for j:=1 to 3 do
              a[kk,i,j]:=(a[kk-1,i,j]+st[kk]*mut[kk,i,j])mod 4;
  for i:=1 to 3 do
      for j:=1 to 3 do
          if a[kk,i,j]<>0 then exit;
  react;
end;

begin
  mo:=28;
  write('Type input file name ');
  readln(s);
  assign(f,s);
  reset(f);
  readln(f,init[1,1],init[1,2],init[1,3]);
  readln(f,init[2,1],init[2,2],init[2,3]);
  readln(f,init[3,1],init[3,2],init[3,3]);
  close(f);
  kk:=1;
  a[0]:=init;
  for i:=1 to 9 do st[i]:=-1;
  while kk>0 do
    begin
      inc(st[kk]);
      if st[kk]>3 then
         begin
           st[kk]:=-1;
           dec(kk);
         end
         else
         begin
           m:=0;
           for i:=1 to kk do m:=m+st[i];
           if m<mo then calcul;
           if m<mo then if kk<9 then inc(kk);
         end;
    end;
  for i:=1 to 9 do
      for j:=1 to sol[i] do
          write(i,' ');
  writeln;
  readkey;
end.
----------------------------------------------
Solutia 5 (Catalin Francu)
program Ceasuri;
type IntegerVector=array[1..9] of Integer;
const Transf:array[1..9] of IntegerVector=
     ((3,3,3,3,3,2,3,2,0),
      (2,3,2,3,2,3,1,0,1),
      (3,3,3,2,3,3,0,2,3),
      (2,3,1,3,2,0,2,3,1),
      (2,3,2,3,1,3,2,3,2),
      (1,3,2,0,2,3,1,3,2),
      (3,2,0,3,3,2,3,3,3),
      (1,0,1,3,2,3,2,3,2),
      (0,2,3,2,3,3,3,3,3));
{ Transformarile necesare pentru a misca un singur ceas cu o pozitie }
var Initial,Moves:IntegerVector;

procedure ReadData;
var FileName:String;
    i:Integer;
begin
  Write('Numele fisierului de intrare: ');ReadLn(FileName);
  Assign(Input,FileName);Reset(Input);
  for i:=1 to 9 do Read(Initial[i]);
  Close(Input);
end;

procedure Turn;
var i,j:Integer;
begin
  for i:=1 to 9 do Moves[i]:=0;
  for i:=1 to 9 do
    if Initial[i]>0
      then for j:=1 to 9 do
              Inc(Moves[j],(4-Initial[i])*Transf[i,j]);
end;

procedure WriteSolution;
var i,j:Integer;
begin
  for i:=1 to 9 do
    for j:=1 to Moves[i] mod 4 do
      Write(i,' ');
  WriteLn;
end;

begin
  ReadData;
  Turn;
  WriteSolution;
end.
-------------------------------------
